Wakacje

Limit pamięci: 96 MB

Bajtazar planuje wybrać dni, w których weźmie urlop. Opiera się on na prognozie pogody na najbliższe dni. Interesują go tylko najwyższe temperatury przewidziane na każdy dzień.

Bajtazar dodatkowo jest ograniczony warunkami postawionymi przez szefa. W ciągu każdych kolejnych dni może wziąć co najwyżej dni urlopu. Jak najlepiej rozplanować wakacje, aby suma temperatur w dniach urlopu była jak największa?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (). W drugim wierszu znajduje się liczb całkowitych dodatnich nie większych niż opisujących temperatury przewidziane na każdy z kolejnych dni.

Wyjście

Na wyjściu należy wypisać jedną liczbę całkowitą - maksymalną sumę temperatur w ciągu dni urlopowych wybranych zgodnie z ograniczeniem narzuconym przez szefa.

Przykład

Dla danych wejściowych:

5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35

poprawną odpowiedzią jest:

195

Autor zadania: Jakub Pachocki.